Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 8 На тему: «Методи сортуваня. Сортування на деревах» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: Семчишин Ю. Б. Коротєєва Т. О. Вовчак І. Г. Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування на деревах. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування на деревах. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування на деревах. ТЕОРЕТИЧНІ ВІДОМОСТІ Метод вибірки з дерева. Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 1 видно, що задана послідовність буде впорядкована у низхідному порядку за 10-1=9 кроків. Сумарний час виконання такого сортування приблизно пропорційний величині п log2 n . Існує декілька модифікацій цього алгоритму, які скорочують цей час.
Рис. 1. Схема сортування методом вибірки з дерева: а - послідовність з десяти чисел для відбору першого найбільшого елемента; б - вибір другого найбільшого елемента. РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://www.wikipedia.org/. Donald Ervin Knuth «The Art of Computer Programming». 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм сортування на деревах. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи сортування? Який метод сортування був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість сортування? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами сортування вам відомими. Наскільки являється ефективним даний метод сортування? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?